package greedy;


// 按道理是两个体重最接近limit 的先上船   但是  假如体重为 1 2 4 5， limit=7，
// 如果 5,2 能组队  2肯定能和5左边的组队  总队数是不变的
// 很明显(5,2)组队就很棒。可是假如我不让(5,2)组队，而让(5,1)组队呢，
// 此时我们只需考虑一个问题，就是这种组队方案，会不会令2找不到配对的伙伴。
// 答案是，不会！因为2可以和最胖的组队，那么他就可以和任何人组队，所以2一定能找到另一半的，也就是说总的组队人数不会减少！

import java.util.Arrays;

public class 救生艇_881 {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int thin = 0,fat = people.length -1, boat = 0;
        while (thin <= fat) {
            boat ++;
            // 相等的时候不用考虑求和了  直接 fat-- and boat ++ 即可
            if(people[thin] + people[fat] <= limit) {
                thin ++;
            }
            fat --;
        }
        return  boat;
    }

    public static void main(String[] args) {
        new 救生艇_881().numRescueBoats(new int[]{1,2,2,3}, 3);
    }
}
